// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-08 16:10
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.TREE;

import com.DataStruct.Tree.TwoBinaryTree.TreeNode;
import com.DataStruct.Tree.TwoBinaryTree.Utils;
import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.List;

public class PathSum {
    /**
     * 全局变量 -> 用于存储结果列表
     */
    List<List<Integer>> ans = new ArrayList<>();

    /**
     * 遍历二叉树的同时获取二叉树从根节点到叶子的路径和路径和
     * 需要使用回溯算法
     */
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<Integer> path = new ArrayList<>();
        preSearch(root, path, targetSum, 0);
        return ans;
    }

    /**
     * 二叉树的先序遍历-> 遍历过程中对于节点总和的变化需要使用回溯算法
     * 路径的保存使用列表-> 同样需要使用回溯算法
     *
     * @param root      根节点
     * @param path      路径列表
     * @param targetSum 目标路径和
     * @param sum       当前路径总和
     */
    private void preSearch(TreeNode root, List<Integer> path, int targetSum, int sum) {
        if (root == null) {
            return;
        }
        sum += root.val;
        path.add(root.val);
        if (root.left == null && root.right == null) {
            if (sum == targetSum) {
                // 当前节点是叶子节点，并且路径和达到目标路径和 -> 进行回溯
                List<Integer> tmp = new ArrayList<>(path);
                ans.add(tmp);
            }
        }
        if (root.left != null) {
            preSearch(root.left, path, targetSum, sum);
        }
        if (root.right != null) {
            preSearch(root.right, path, targetSum, sum);
        }
        // 进行回溯
        path.remove(path.size() - 1);

    }


    @Test
    public void shout() {
        int[] nodes = {5, 4, 8, 11, -1, 13, 4, 7, 2, -1, -1, 5, 1};
        int targetSum = 22;
        Utils utils = new Utils();
        TreeNode<Integer> root = utils.constructTreeBySequence(nodes);
        System.out.println(pathSum(root, targetSum));
    }


}
